package com.lw.leetcode.sort.b;

import java.util.*;

/**
 * str
 * 522. 最长特殊序列 II
 *
 * @Author liw
 * @Date 2021/6/30 21:38
 * @Version 1.0
 */
public class FindLUSlength {

    public static void main(String[] args) {
        FindLUSlength test = new FindLUSlength();
//        String[] arr = {"a","b","c","d","e","f","a","b","c","d","e","f"};
//        String[] arr = {"abcdef", "add"};
//        String[] arr = {"aaa", "aaa", "aa"};
        String[] arr = {"j","j","viez","ogk","ogk","lfn","ypmhwx","ypmhwx","m","m","ak","ivivzoncju","ivivzoncju","wmybi","wmybi","dyzfjg","dyzfjg"};
//        String[] arr = {"aba", "cdc", "eae"};
//        String[] arr = {"aabbcc", "aabbcc","cb","abc"};
//        String[] arr = {"aaa", "acb"};
//        String[] arr = {"aabbcc", "aabbcc","c","e","aabbcd"};
        int luSlength = test.findLUSlength(arr);
        System.out.println(luSlength);
    }

    /*
    1：先把字符串排序，按照长度从大到小排序。
    2：遍历字符串，判断其是否是大于等于它长度的字符串的子串，若是，则下一个，若不是，则返回其长度为所求。
     */
    public int findLUSlength(String[] strs) {
        Arrays.sort(strs, (a, b) ->  b.length() - a.length());
        System.out.println(Arrays.toString(strs));
        for (int i = 0, j; i < strs.length; i++) {
            boolean flag = true;
            for (j = 0; j < strs.length; j++) {
                if (i == j) {
                    continue;
                }
                if (find(strs[j], strs[i])) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return strs[i].length();
            }
        }
        return -1;
    }

    public int findLUSlength3(String[] strs) {
        int length = strs.length;
        Arrays.sort(strs, (a, b) ->  b.length() - a.length());
        System.out.println(Arrays.toString(strs));
        for (int i = 0; i < length; i++) {
            boolean flag = true;
            String value = strs[i];
            int l = value.length();
            for (int j = 0; j < length; j++) {
                if (i == j) {
                    continue;
                }
                if (l > strs[j].length()) {
                    break;
                }
                if (find(strs[j], value)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return value.length();
            }
        }
        return -1;
    }

    public int findLUSlength2(String[] strs) {
        int length = strs.length - 1;
        Arrays.sort(strs, (a, b) -> a.length() == b.length() ? a.compareTo(b) : b.length() - a.length());
        System.out.println(Arrays.toString(strs));

        List<String> set = new ArrayList<>();
        String value;
        for (int i = 0; i < length; i++) {
            value = strs[i];
            boolean flag = true;
            for (String s : set) {
                if (find(s, value)) {
                    flag = false;
                    break;
                }
            }
            if (value.equals(strs[i + 1])) {
                if (flag) {
                    set.add(value);
                }
                int j;
                for (j = i + 1; j <= length; j++) {
                    if (!value.equals(strs[j])) {
                        break;
                    }
                }
                i = j - 1;
            } else {
                if (flag) {
                    return value.length();
                }
            }
        }
        value = strs[length];
        if (!value.equals(strs[length - 1])) {
            boolean flag = true;
            for (String s : set) {
                if (find(s, value)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return value.length();
            }
        }
        return -1;
    }

    /**
     * 判断 b 是否是 a 的子串
     *
     * @param a 字符串
     * @param b 字符串
     * @return b 是否是 a 的子串
     */
    private boolean find(String a, String b) {
        int m = a.length();
        int n = b.length();
        int i = 0;
        int j = 0;
        while (i < m && j < n) {
            if (a.charAt(i) == b.charAt(j)) {
                j++;
            }
            i++;
        }
        return j == n;
    }

    /**
     * 暴力方法
     */
    public int findLUSlength4(String[] strs) {
        int length = strs.length;
        char[][] arr = new char[length][];
        for (int i = 0; i < length; i++) {
            String str = strs[i];
            arr[i] = str.toCharArray();
        }
        int max = -1;
        for (int i = 0; i < length; i++) {
            char[] cs = arr[i];
            int l = cs.length;
            char[] items = new char[l];
            int end = (1 << l) - 1;
            for (int val = 1; val <= end; val++) {
                int index = getArr(cs, val, items);
                boolean f = true;
                for (int j = 0; j < length; j++) {
                    if (i == j) {
                        continue;
                    }
                    if (!find(items, index, arr[j])) {
                        f = false;
                        break;
                    }
                }
                if (f) {
                    max = Math.max(max, l - index);
                }
            }
        }
        return max;
    }

    private boolean find(char[] items, int s1, char[] others) {
        int e1 = items.length;
        int e2 = others.length;
        int s2 = 0;
        while (s1 < e1 && s2 < e2) {
            if (items[s1] == others[s2]) {
                s1++;
                s2++;
            } else {
                s2++;
            }
        }
        return s1 != e1;
    }

    private int getArr(char[] cs, int val, char[] items) {
        int end = cs.length - 1;
        int index = end;
        while (val != 0) {
            if ((val & 1) == 1) {
                items[index--] = cs[end--];
            } else {
                end--;
            }
            val >>= 1;
        }
        return index + 1;
    }
}
